#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define  BASE_HASHTABLE_SIZE  4096
//hash table
size_t hash(const char*str,size_t l)
{
	size_t h = 5 ^ l;
	size_t l1 = 0;
	size_t step = 1;
	for (l1 = l; l1 > step; l1-=step)
	{
		h = h ^ ((h << 5) + (h >> 2) + str[l1-1]);
	}
	return h;
}

typedef struct _HashNode
{
	const char *key;
	void *value;
	struct _HashNode *next;
}HashNode;
typedef struct _HashTable{
	HashNode *table;
	size_t n;
	size_t size;
}*HashTable;

HashTable _hash_create(size_t size)
{
	HashTable table = malloc(sizeof(struct _HashTable));
	memset(table, 0, sizeof(struct _HashTable));
	table->size = size;
	table->table = malloc(sizeof(HashNode) * table->size);
	memset(table->table, 0, sizeof(HashNode) * table->size);
	table->n = 0;
	return table;
}


HashTable hash_create()
{
	return _hash_create(BASE_HASHTABLE_SIZE);
}

void hash_rehash(HashTable table);

void hash_insert(HashTable table, const char *key, void *value){
	size_t h = hash(key, strlen(key));
	size_t index = h % table->size;
	if (table->n == table->size){
		hash_rehash(table);
	}
	HashNode * node = &table->table[index];
	if (node->key == NULL){
		node->key = key;
		node->value = value;
	}
	else{
		HashNode *current = &node;
		while ((current = current->next) != NULL){}
		current->key = key;
		current->value = value;
	}

}


void hash_rehash(HashTable table)
{
	size_t nsize = table->size + BASE_HASHTABLE_SIZE;
	HashTable nt = _hash_create(nsize);
	for (int i = 0; i < table->size;i++){
		HashNode node = table->table[i];
		if(node.key!=NULL){
			hash_insert(nt, node.key, node.value);
		}
	}
	free(table->table);
	table->n = nt->n;
	table->size = nt->size;
	table->table = nt->table;
	free(nt);
}



void hash_set(HashTable table,const char *key,void *value){
	size_t h = hash(key, strlen(key));
	size_t index = h % table->size;
	HashNode node = table->table[index];
	if (node.key == key){
		node.value = value;
	}
	else{
		HashNode *current = &node;
		while ((current = current->next) != NULL)
		{
			if (current->key == key){
				current->value = value;
				break;
			}
		}
	}
}


void* hash_get(HashTable table,const char *key){
	size_t h = hash(key, strlen(key));
	size_t index = h % table->size;
	HashNode *node = &table->table[index];
	if (node->key == key){
		return node->value;
	}
	else{
		HashNode *current = node;
		while ((current = current->next) != NULL)
		{
			if (current->key == key){
				return current->value;
				break;
			}
		}
	}
	return NULL;
}



int main(int argc,char **argv)
{
	printf("Hello World!\n");
	HashTable table = hash_create();
	hash_insert(table, "name", "xiaoyuan");
	hash_insert(table, "age", 23);
	const char* name = hash_get(table, "name");
	int age = hash_get(table, "age");
	printf("name:%s,age:%d\n", name, age);
	system("pause");
	return 0;
}